package com.yohann.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <p>
 * 逆波兰计算器
 * </p>
 *
 * @author Yohann
 * @since 2020/9/24
 */
public class PolandCalculator {
    public static void main(String[] args) {
        //逆波兰表达式 (3+4)*5-6
        String suffixExpression = "1+((2+3)*4)-5";
        List<String> expressionList = toSuffixExpressionList(toInfixExpressionList(suffixExpression));
        System.out.println(expressionList);
//        //将表达式存入ArrayList中
//        List<String> list = getListString(suffixExpression);
//
        //计算
        int result = calculate(expressionList);
        System.out.println(result);
    }

    //将表达式存入ArrayList中
    public static List<String> getListString(String suffixExpression) {
        String[] strings = suffixExpression.split(" ");

        List<String> list = new ArrayList<>();
        for (String s : strings) {
            list.add(s);
        }

        return list;
    }

    //完成对逆波兰表达式的运算
    public static int calculate(List<String> list) {
        //创建栈
        Stack<String> stack = new Stack<>();

        for (String item : list) {
            //如果是数字 直接入栈
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                //如果是运算符号弹出两个数字进行运算
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int result = 0;

                if (item.equals("+")) {
                    result = num1 + num2;
                } else if (item.equals("-")) {
                    result = num2 - num1;
                } else if (item.equals("*")) {
                    result = num1 * num2;
                } else {
                    result = num2 / num1;
                }

                //将结果返回栈中
                stack.push(result + "");
            }
        }

        return Integer.parseInt(stack.pop());
    }

    //中缀表达式转list
    public static List<String> toInfixExpressionList(String s) {
        List<String> list = new ArrayList<>();
        int i = 0;
        String str;
        char c;

        do {
            //如果c是非数字，直接加入list
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add("" + c);
                i++;
            } else {
                //如果是数字 需要考虑多位数
                str = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                list.add(str);
            }
        } while (i < s.length());

        return list;
    }

    //中缀表达式转后缀表达式
    public static List<String> toSuffixExpressionList(List<String> list) {
        //符号暂存栈
        Stack<String> stack = new Stack<>();
        //结果集
        List<String> stringList = new ArrayList<>();

        for (String s : list) {
            if (s.matches("\\d+")) {
                stringList.add(s);
            } else if (s.equals("(")) {
                stack.push(s);
            } else if (s.equals(")")) {
                //如果是右括号")" 依次弹出栈中运算符 加入结果集 直到左括号为止，此时丢弃一对括号
                while (!stack.peek().equals("(")) {
                    stringList.add(stack.pop());
                }

                //去掉左括号
                stack.pop();
            } else {
                //运算符优先级别小于栈顶运算符 栈内弹出运算符 加入结果集中
                while (stack.size() != 0 && Operation.getValue(stack.peek()) >= Operation.getValue(s)) {
                    stringList.add(stack.pop());
                }
                stack.push(s);
            }
        }

        //将剩下的运算符弹出
        while (stack.size() != 0) {
            stringList.add(stack.pop());
        }

        return stringList;
    }
}

class Operation {
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 1;
    private static final int DIV = 1;

    public static int getValue(String operation) {
        int result = 0;

        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                break;
        }

        return result;
    }
}